package tree;

/**
 * @author : Rookie
 * @description : 判断一个树是不是平衡二叉树
 * @date : 2023/10/13
 */
public class BalanceBinaryTree {

    public static void main(String[] args) {
//        int[] input = new int[] {1,2,2,3,3,-1,-1,4,4};
        int[] input = {3, 9, 20, -1, -1, 15, 7};
        TreeNode root = BinaryTreeUtil.buildTree(input);
        System.out.println(getHeight(root) == -1);
    }

    /**
     * 获取一个树的高度 高度和深度刚好是相反的，最高层的高度最大，深度最小
     * 因为要获取高度 是从下往上处理节点，所以是后序遍历
     * @param root
     * @return
     */
    private static int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;

        // 左右子树的高度差绝对值大于1 认为是不平衡的
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            // 左右子树都符合条件时，当前高度为1+左右高度最大值
            return 1+Math.max(leftHeight,rightHeight);
        }
    }
}
